#include <iostream>
#include <cstring>
#include <queue>
#include <cassert>

#include "BST.h"
#include "RBT.h"
#include "AVLTree.h"
#include "SpalyTree.h"
#include "Treap.h"
#include "SBT.h"
#include "TestBinarySearchTreeHelper.h"

void testSBT();

void testRandromArray(){

    int n = 1000000;
    int range = n*10;

    BST<int,int>* bst = new BST<int,int>();
    RedBlackTree<int,int>* rbt = new RedBlackTree<int,int>();
    AVLTree<int,int>* avl = new AVLTree<int,int>();
    SplayTree<int,int>* splay = new SplayTree<int,int>();
    Treap<int,int>* treap = new Treap<int,int>();
    SBT<int,int>* sbt = new SBT<int,int>();
    cout << "Test for Random Array, size = " << n << ", range [1," << range << "]" << endl;
    int *arr1 =  TestBinarySearchTreeHelper::generateRandomArray(n,1,range);
    int *arr2 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    int *arr3 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    int *arr4 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    int *arr5 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    int *arr6 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    TestBinarySearchTreeHelper::test("binary search tree",bst,arr1,n);
    TestBinarySearchTreeHelper::test("red black tree",rbt,arr2,n);
////    int arr3[] = {197, 626, 635, 526, 145, 623, 773, 509, 883, 931, 922, 171, 248, 758, 840, 948, 844, 170, 970, 48, 620, 475, 124, 521, 200, 763, 527, 249, 989, 927, 218, 63, 861, 285, 229, 133, 829, 751, 211, 758, 924, 409, 160, 20, 628, 358, 630, 664, 922, 552, 826, 114, 519, 648, 228, 630, 878, 53, 631, 633, 206, 950, 638, 61, 207, 340, 356, 249, 131, 717, 866, 280, 16, 960, 503, 815, 288, 183, 607, 158, 182, 658, 953, 773, 513, 178, 659, 511, 45, 666, 607, 70, 370, 233, 268, 854, 470, 486, 115, 22};
    TestBinarySearchTreeHelper::test("avl tree",avl,arr3,n);
//    int arr4[] = {786,436,871,46,930,934,608,405,744,387,588,315,994,127,200,948,235,700,384,876,259,107,666,12,315,607,976,882,361,292,832,118,896,564,497,746,109,509,399,353,210,717,368,313,41,972,997,820,869,139,789,516,792,627,147,112,507,12,991,0,418,583,985,4,701,840,129,963,686,106,930,785,923,486,38,15,784,562,385,659,364,373,510,360,386,265,275,332,762,494,238,627,694,406,713,736,460,732,72,820};
//    for(int i = 0 ;i<n;i++){
//        cout<<arr4[i]<<",";
//    }
    TestBinarySearchTreeHelper::test("splay tree",splay,arr4,n);
    TestBinarySearchTreeHelper::test("treap tree",treap,arr5,n);
    TestBinarySearchTreeHelper::test("sbt tree",sbt,arr6,n);


    delete bst;
    delete rbt;
    delete avl;
    delete splay;
    delete treap;
    delete sbt;

    delete arr1;
    delete arr2;
    delete arr3;
    delete arr4;
    delete arr5;
    delete arr6;
}

void testNearlyOrderedArray( int swaptimes) {
    int n = 10000;
    BST<int,int>* bst = new BST<int,int>();
    RedBlackTree<int,int>* rbt = new RedBlackTree<int,int>();
    AVLTree<int,int>* avl = new AVLTree<int,int>();
    SplayTree<int,int>* splay = new SplayTree<int,int>();
    Treap<int,int>* treap = new Treap<int,int>();
    SBT<int,int>* sbt = new SBT<int,int>();
    cout << "Test for Nearly Ordered Array, size = " << n << ", swaptimes [" << swaptimes << "]" << endl;
    int *arr1 =  TestBinarySearchTreeHelper::generateNearlyOrderedArray(n,swaptimes);
    int *arr2 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    int *arr3 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    int *arr4 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    int *arr5 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    int *arr6 =  TestBinarySearchTreeHelper::copyIntArray(arr1,n);
    TestBinarySearchTreeHelper::test("binary search tree",bst,arr1,n);
    TestBinarySearchTreeHelper::test("red black tree",rbt,arr2,n);
    TestBinarySearchTreeHelper::test("avl tree",avl,arr3,n);
    TestBinarySearchTreeHelper::test("splay tree",splay,arr4,n);
    TestBinarySearchTreeHelper::test("treap tree",treap,arr5,n);
    TestBinarySearchTreeHelper::test("sbt tree",sbt,arr6,n);

    delete bst;
    delete rbt;
    delete avl;
    delete splay;
    delete treap;
    delete sbt;

    delete arr1;
    delete arr2;
    delete arr3;
    delete arr4;
    delete arr5;
    delete arr6;
}

void testNearlyOrderedArray() {
    testNearlyOrderedArray(0);
    cout<<"----------------------------------------------------"<<endl;
    testNearlyOrderedArray(100);
}

void testSBT() {
    int n = 1000;
    SBT<int,int>* sbt = new SBT<int,int>();
    int *arr1 =  TestBinarySearchTreeHelper::generateRandomArray(n,0,n);
//    int arr1[] =  {7,4,30,20,0,4,23,6,16,15,18,21,2,9,7,11,8,3,20,20,26,17,16,0,0,17,3,4,6,17};
    for(int i = 0 ;i<n;i++){
//        cout<<arr1[i]<<",";
        sbt->put(arr1[i],arr1[i]);
        sbt->check();
    }
    for(int i = 0 ;i<n;i++){
//        cout<<arr1[i]<<",";
        sbt->remove(arr1[i]);
        sbt->check();
    }

}

int main() {
    testRandromArray();
    cout<<"----------------------------------------------------"<<endl;
    testNearlyOrderedArray();
//    testSBT();

    return 0;
}